# 请设计一个栈，除了常规栈支持的pop与push函数以外，还支持min函数，该函数返回栈元素中的最小值。执行push、pop和min操作的时间复杂度必须为O(
# 1)。 
#  示例： MinStack minStack = new MinStack(); minStack.push(-2); minStack.push(0); 
# minStack.push(-3); minStack.getMin();   --> 返回 -3. minStack.pop(); minStack.top(
# ); --> 返回 0. minStack.getMin(); --> 返回 -2. 
# 
#  Related Topics 栈 设计 👍 102 👎 0
import sys


# leetcode submit region begin(Prohibit modification and deletion)
class MinStack:

    def __init__(self):
        """
        initialize your data structure here.
        """
        self.stack = []
        self.minStcak = []

    def push(self, x: int) -> None:
        self.stack.append(x)
        if not self.minStcak or x <= self.minStcak[-1]:
            # 如果辅助栈为空或者push元素小于辅助栈栈顶元素（栈顶元素恒为辅助栈的最小值，本质上辅助栈就是一个递减栈），则把push元素压入辅助栈
            self.minStcak.append(x)

    def pop(self) -> None:
        p = self.stack.pop()
        # 若最小值被pop出去了，则栈中已不存在这个值，辅助栈中的这个值也应该同步去掉
        if p == self.minStcak[-1]:
            self.minStcak.pop()

    def top(self) -> int:
        return self.stack[-1]

    def getMin(self) -> int:
        return self.minStcak[-1]

# Your MinStack object will be instantiated and called as such:
# obj = MinStack()
# obj.push(x)
# obj.pop()
# param_3 = obj.top()
# param_4 = obj.getMin()
# leetcode submit region end(Prohibit modification and deletion)
